題目:給定一個包含 n 個不同整數的陣列 nums,每個整數都在範圍 [0, n] 之間。
請找出陣列中缺少的那個數字

解法一

- 直觀但慢
- 依序檢查 0 ~ n 的每個數字,看它是否存在於陣列中。
沒出現的那個,就是缺少的數
註解
- len(nums):陣列長度 n
- 用 range(n + 1) 代表所有可能的數字(包含 n)
- 用 in 檢查是否存在陣列中
- 時間複雜度 O(n²),因為 in 每次都要掃整個陣列
理解
- 想像你有一份 0~n 的點名表,一個一個名字叫:
「0 在嗎?1 在嗎?…」
結果發現有人沒來,那個人就是缺少的數。
解法二

- 查找速度快
- Hash Set(集合法)
- 把陣列轉成 set(集合),再檢查 0~n 哪個不在集合裡
註解
- set(nums):轉成集合,查找效率 O(1)
- 依序檢查每個數是否存在於集合中
- 時間 O(n),空間 O(n)
理解
- 這就像你用「快速查名冊」代替一張一張點名
集合幫你快速知道誰有來誰沒來,速度快多了
解法三

- 數學法(Sum Formula)
- 利用數學公式:
前 n 個自然數總和是 n * (n + 1) / 2
缺少的數 = 理論總和 − 實際總和
註解
- n * (n + 1) // 2:期望的總和(完整序列)
- sum(nums):實際陣列的總和
- 兩者相減就得到缺少的數字
- 時間 O(n),空間 O(1)
理解
- 這就像你有一份完整的「總分清單」,但有一項缺了,
用總分減掉現有的分數總和,就知道誰沒交作業